package sword.offer;

/**
 * 约瑟夫环问题
 * 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
 *
 * 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
 * 链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class SixtyTwo {
    /**
     * 这道题用到的是逆向思维。
     * 使用反推的方式来得到最终答案。
     *
     * 首先，最后剩下的数字，在其下标中肯定为0，因为只剩它一个了
     * 那么上一轮 这个数字 一定在 （0+m）% i , 其中m就是题目中的m，i表示上一轮剩余的数，显然i为2。
     * 如果m=3，那么式子的值就是1，也就是说 在上一轮中，该数字在下标为1才能够保留下来。
     * 那么上上轮  则为（1 + m） % 2, 如果m为三的话，其值就为2
     * 以此类推，直到i为指定的n时。
     * */
    class Solution {
        public int lastRemaining(int n, int m) {
            int ans = 0;
            for(int i = 2; i <= n; i++){
                ans = (ans + m) % i;
            }
            return ans;
        }
    }
}
